package impl;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

public class HeapSorter extends AbstractSorter {

    public HeapSorter() {
        super(SorterType.HEAP);
    }

    public <T> void sort(Comparator<T> comparator, List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }

    protected <T> void sort(Comparator<T> comparator, List<T> list, int left, int N) {
        for (int k = (N - 1) / 2; k >= left; k--) {
            sink(comparator, list, k, N);
        }
        while (N > left) {
            swap(list, left, N--);
            sink(comparator, list, left, N);
        }
    }

    private <T> void sink(Comparator<T> comparator, List<T> list, int k, int N) {
        while ((((k + 1) * 2) - 1) <= N) {
            int j = ((k + 1) * 2) - 1;
            if (j < N && !greater(comparator, list, j, j + 1)) {
                j++;
            }
             if (greater(comparator, list, k, j))
                break;
            swap(list, k, j);
            k = j;
        }
    }
}